package metier;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * Classe de pathfinding utilisant l'algorithme A*
 *
 * @author Thomas Folgueral
 * @author Julien Pernot
 * @author Guillaume Peyet
 * @author Guillaume Sainthillier
 */
public class Astar implements IDeplacable {
	private Carte carte;
	private Position depart;
	private Position arrivee;

    /**
     * Determine les positions successives à effecter en fonction des élements présents sur la carte
     * @param carte la carte sur laquelle l'élèment est placé
     * @param positionDepart la position de départ de l'élèment
     * @param positionArrivee la position d'arrivée de l'élèment
     * @return une liste des positions à effectuer
     */
	@Override
    public ArrayList<Position> pathfinding(Carte carte, Position positionDepart, Position positionArrivee) {
		if (positionDepart == null || positionArrivee == null)
			return new ArrayList<Position>();
		
		this.carte = carte;
		this.depart = positionDepart;
		this.arrivee = positionArrivee;
		
		// On crée le graphe à parcourrir
		Node[][] map = new Node[carte.getLargeur()][carte.getLongueur()];
		
		for (int x = 0 ; x < carte.getLargeur() ; x++) {
			for (int y = 0 ; y < carte.getLongueur() ; y++) {
				map[x][y] = new Node(x, y);
			}
		}
		
		SortedList openList = new SortedList();
		ArrayList<Node> closedList = new ArrayList<Node>();
		
		// etat initial
		int departX = this.depart.getX();
        int departY = this.depart.getY();
		int arriveeX = this.arrivee.getX();
		int arriveeY = this.arrivee.getY();
		map[departX][departY].cost = 0;
		map[departX][departY].heuristic = this.distance(this.depart, this.arrivee);
		map[departX][departY].depth = 0;
		map[departX][departY].parent = null;
		
		openList.add(map[departX][departY]);
		
		while(openList.size() != 0) {
			Node current = openList.first();
			
			// si on est sur le noeud d'arrivée on a le chemin final
			if (current == map[arriveeX][arriveeY])
				break;
			
			// On transfère le noeud courrant dans la closed list
			openList.remove(current);
			closedList.add(current);
			
			for (int voisinX = current.x - 1 ; voisinX <= current.x + 1 ; voisinX++) {
				for (int voisinY = current.y - 1 ; voisinY <= current.y + 1 ; voisinY++) {
					if (!(voisinX == current.x && voisinY == current.y) && this.positionIsValid(voisinX, voisinY)) {
						Node voisin = map[voisinX][voisinY];
						
						if (closedList.contains(voisin)) {
							for (Node closedNode : closedList) {
								if (closedNode == voisin && voisin.cost < closedNode.cost) {
									voisin.cost = current.cost + 1;
									voisin.heuristic = this.distance(new Position(voisinX, voisinY), this.arrivee);
									voisin.parent = current;
									
									closedList.remove(voisin);
									openList.add(voisin);
								}
							}
						} else {
							voisin.cost = current.cost + 1;
							voisin.heuristic = this.distance(new Position(voisinX, voisinY), this.arrivee);
							voisin.parent = current;
							openList.add(voisin);
						}
					}
				}
			}
			
		}
		
		// On calcule le chemin à parcourrir
        ArrayList<Position> cheminReverse = new ArrayList();
		
		if (map[arriveeX][arriveeY].parent != null) {
			Node current = map[arriveeX][arriveeY].parent;
			cheminReverse.add(this.arrivee);
			
			while (current != map[departX][departY]) {
				cheminReverse.add(new Position(current.x, current.y));
				current = map[current.x][current.y].parent;
			}
			
		}
		
		ArrayList<Position> chemin = new ArrayList();
		
		for (int i = cheminReverse.size() - 1 ; i >= 0 ; i--) {
			chemin.add(cheminReverse.get(i));
		}
		
        return chemin;
    }

	private boolean positionIsValid(int voisinX, int voisinY) {
		boolean isValid = true;
		
		if (voisinX < 0 || voisinX >= this.carte.getLargeur() ||
				voisinY < 0 || voisinY >= this.carte.getLongueur())
			isValid = false;
		
		for (Element elem : this.carte.getElements(new Position(voisinX, voisinY))) {
			if (elem instanceof Roche || elem instanceof Nouriturre)
				isValid = false;
		}
		
		return isValid;
	}
	
	private double distance(Position depart, Position arrivee) {
		int departX = depart.getX();
        int departY = depart.getY();
        int arriveeX = arrivee.getX();
        int arriveeY = arrivee.getY();
		int ecartX = Math.abs(arriveeX - departX);
		int ecartY = Math.abs(arriveeY - departY);
		
		double distance = Math.sqrt((ecartX * ecartX) + (ecartY * ecartY));
		return distance;
	}
	
	private class Node implements Comparable {
		private int x;
		private int y;
		private int cost;
		private Node parent;
		private double heuristic;
		private int depth;
		
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		public int setParent(Node parent) {
			depth = parent.depth + 1;
			this.parent = parent;
			
			return depth;
		}
		
		@Override
		public int compareTo(Object other) {
			Node o = (Node) other;
			
			double f = heuristic + cost;
			double of = o.heuristic + o.cost;
			
			if (f < of) {
				return -1;
			} else if (f > of) {
				return 1;
			} else {
				return 0;
			}
		}
	}
	
	private class SortedList {
		private ArrayList<Node> list = new ArrayList<Node>();
		
		public Node first() {
			return list.get(0);
		}
		
		public void clear() {
			list.clear();
		}
		
		public void add(Node node) {
			boolean add = true;
			for (Node elem : list) {
				if (elem.x == node.x && elem.y == node.y) {
					if (node.cost < elem.cost)
						list.remove(elem);
					else
						add = false;
				}
			}
			
			if (add)
				list.add(node);
			Collections.sort(list);
		}
		
		public void remove(Node node) {
			list.remove(node);
		}
		
		public int size() {
			return list.size();
		}
		
		public boolean containsNode(Node node) {
			return list.contains(node);
		}
	}
//    @Override
//    public ArrayList<Position> pathfinding(Carte carte, Position positionDepart, Position positionArrivee) {
//        // on recupere les coordonnees des positions
//        int departX = positionDepart.getX();
//        int departY = positionDepart.getY();
//        int arriveeX = positionArrivee.getX();
//        int arriveeY = positionArrivee.getY();
//
//        // on verifie que les positions donnees sont bien dans la carte
//        int dimX = carte.getLargeur();
//        int dimY = carte.getLongueur();
//
//        if (departX < 0 || departX > dimX
//                || departY < 0 || departY > dimY
//                || arriveeX < 0 || arriveeX > dimX
//                || arriveeY < 0 || arriveeY > dimY) {
//            throw new IllegalArgumentException("La position de depart ou d'arrivee est en dehors de la carte.");
//        }
//
//        // on avance vers la destination pas e pas en ajoutant chaque position au chemin
//        ArrayList<Position> chemin = new ArrayList();
//        while (!(departX == arriveeX && departY == arriveeY)) {
//            if (departX > arriveeX) {
//                departX--;
//            } else if (departX < arriveeX) {
//                departX++;
//            }
//
//            if (departY > arriveeY) {
//                departY--;
//            } else if (departY < arriveeY) {
//                departY++;
//            }
//
//            chemin.add(new Position(departX, departY));
//        }
//        
//        return chemin;
//    }
}
